package TreeNode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinaryTree implements ITreeNode{
    @Override
    public int size(MyNode root) {
        if(root == null){
            return 0;
        }
        return size(root.left) + size(root.right) + 1;
    }

    @Override
    public int getLeafNodeCount(MyNode root) {
        if (root == null) {
            return 0;
        }
        int count = 0;
        if (root.left == null && root.right == null) {
            count++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
        return count;
    }

    @Override
    public int getKLevelNodeCount(MyNode root, int k) {
        if (root == null) {
            return 0;
        }
        if(k==1){
            return 1;
        }
        return getKLevelNodeCount(root.left, k-1) + getKLevelNodeCount(root.right, k-1);
    }

    @Override
    public int getHeight(MyNode root) {
        if (root == null) {
            return 0;
        }
        return abs(root.left,root.right);
    }

    public int abs(MyNode node1,MyNode node2){
        if(node1==null && node2==null){
            return 0;
        }
        int nodeHeight1 = 0;
        int nodeHeight2 = 0;
        if(node1!=null){
            nodeHeight1=abs(node1.left,node1.right);
        }
        if(node2!=null){
            nodeHeight2=abs(node2.left,node2.right);
        }
        if(nodeHeight1>nodeHeight2){
            return nodeHeight1;
        }else{
            return nodeHeight2;
        }
    }

    @Override
    public MyNode Nodefind(MyNode root, int val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }
        MyNode temp = Nodefind(root.left, val);
        if (temp != null) {
            return temp;
        }
        temp = Nodefind(root.right, val);
        if (temp != null) {
            return temp;
        }

        return null;
    }

    @Override
    public void levelOrder(MyNode root) {
        if(root == null) {
            return;
        }
        Queue<MyNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            MyNode cur = queue.poll();
            System.out.print(cur.val+" ");

            if(cur.left != null) {
                queue.offer(cur.left);
            }
            if(cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }

    @Override
    public boolean isCompleteTree(MyNode root) {

        if(root == null) {
            return true;
        }
        Queue<MyNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            MyNode cur = queue.poll();
            if(cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;//结束这个循环
            }
        }
        //需要判断队列当中 是否有非空的元素
        while (!queue.isEmpty()) {
            //一个元素 一个元素 出队来判断 是不是空
            MyNode tmp = queue.peek();
            if(tmp == null) {
                queue.poll();
            }else {
                return false;
            }
        }
        return true;
    }

    //前序遍历
    void preOrder(MyNode root) {
        if (root == null) {
            return;
        }
        Stack<MyNode> stack = new Stack<>();
        MyNode curr = root;
        while (curr!=null&&!stack.isEmpty()) {
            while(curr!=null){
                stack.push(curr);
                System.out.println(curr.val+" ");
                curr=curr.left;
            }
            MyNode top=stack.pop();
            curr=top.right;
        }
    }

    //中序遍历
    void inOrder(MyNode root) {
        if (root == null) {
            return;
        }
        Stack<MyNode> stack = new Stack<>();
        MyNode curr = root;
        while (curr!=null&&!stack.isEmpty()) {
            while(curr!=null){
                stack.push(curr);
                curr=curr.left;
            }
            MyNode top=stack.pop();
            System.out.println(top.val+" ");
            curr=top.right;
        }
    }

    //后续遍历
    void postOrderNor(MyNode root){
        if(root == null) {
            return;
        }
        Stack<MyNode> stack = new Stack<>();
        MyNode cur = root;
        MyNode prev = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            MyNode top = stack.peek();

            if(top.right == null || top.right == prev) {
                System.out.print(top.val+" ");
                stack.pop();
                prev = top;
            }else {
                cur = top.right;
            }
        }
    }
}
